/** 组合
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
输入: n = 4, k = 2 
输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
 */
/**
 *! 【无序】设置 startIndex-需要去重
 *! 【元素不重复， index+1】
 *! 【剪枝优化】i<= n-k+path.length+1
 优化条件： 如果剩余的元素都不能满足K个了 就没有遍历的必要了
 开始位置 i  1
 剩余: n-i  3
 需要: k-path.length 1
 n-i>=k-path.length
 【i<= n-k+path.length+1】  i<= 3-2+1+1 i<=3  需要取到3闭合 
 */
var combine = function(n, k) {
  let result = [];
  let path = [];
  const backTracking = (n, k, index) =>  {
    if(path.length == k) {
      result.push(path.slice()) //!加入path副本，不随path改变而改变
      return;
    }
    // for(let i=index; i<=n;i++) { //【不剪枝】横向i～n
    for(let i=index; i<=n-k+path.length+1;i++) { //!【剪枝】
      path.push(i); //记录下第一层取i的情况
      backTracking(n, k, i+1) //!递归k-1层，【i+1元素不重复】
      path.pop(); //回溯，删除path最后一项
    }
    //回溯函数的返回值一般为void
  }
  backTracking(n,k,1);
  return result;
}

const n = 4, k = 2;
console.log('组合',combine(n,k));